package algorithm_demo.demo_advanced;

import java.util.Arrays;
import java.util.LinkedList;

/*
 * 假设一个固定大小为W的窗口，依次划过arr，返回每一次滑出状态的最大值
 * 例如：arr = [4,3,5,4,3,3,6,7],W=3
 * 返回：[5,5,5,4,6,7]
 * */
public class Code01_SlidingWindowMaxArray {
    public static int[] getMaxWindows(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        //双端队列，其中放的是位置,arr[位置],头部代表的数（大->小）尾部
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            while(!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]){
                qmax.pollLast();
            }
            qmax.addLast(i);
            if (qmax.peekFirst() == i-w){
                qmax.pollFirst();
            }
            if (i>=w-1){
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {4,3,5,4,3,3,6,7};
        int W = 3;
        int[] maxWindows = getMaxWindows(arr, W);
        System.out.println(Arrays.toString(maxWindows));
    }
}
